from typing import *


class Solution:

    def possibleToStamp(self, grid: List[List[int]], stampHeight: int,
                        stampWidth: int) -> bool:
        m, n = len(grid), len(grid[0])

        def pre_sum_array2(grid):
            m, n = len(grid), len(grid[0])
            sums = [[0] * n for _ in range(m)]
            for i in range(m):
                for j in range(n):
                    if i == 0 and j == 0:
                        sums[i][j] = grid[i][j]
                    elif i == 0:
                        sums[i][j] = grid[i][j] + sums[i][j - 1]
                    elif j == 0:
                        sums[i][j] = grid[i][j] + sums[i - 1][j]
                    else:
                        sums[i][j] = grid[i][j] + sums[i - 1][j] + sums[i][
                            j - 1] - sums[i - 1][j - 1]
            return sums

        def pre_sum_array2_area_tot(grid, left_top, right_bottom,
                                    default_false):
            m, n = len(grid), len(grid[0])
            a, b = left_top[0], left_top[1]
            c, d = right_bottom[0], right_bottom[1]
            if a < 0 or b < 0 or c >= m or d >= n:
                return default_false
            if a == 0 and b == 0:
                return grid[c][d]
            if a != 0 and b != 0:
                return grid[c][d] - grid[c][b - 1] - grid[a - 1][d] + grid[
                    a - 1][b - 1]
            if a == 0:
                return grid[c][d] - grid[c][b - 1]
            return grid[c][d] - grid[a - 1][d]

        tips = [[0] * n for _ in range(m)]

        sums_grid = pre_sum_array2(grid)

        for i in range(m):
            for j in range(n):
                flag = pre_sum_array2_area_tot(
                    sums_grid, (i, j),
                    (i + stampHeight - 1, j + stampWidth - 1), 1)
                if flag == 0:
                    tips[i][j] = 1
        sums_tips = pre_sum_array2(tips)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and pre_sum_array2_area_tot(
                        sums_tips,
                    (max(i - stampHeight + 1, 0), max(j - stampWidth + 1, 0)),
                    (i, j), 0) == 0:
                    return False

        return True


s = Solution()
# print(
#     s.possibleToStamp(grid=[[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0],
#                             [1, 0, 0, 0], [1, 0, 0, 0]],
#                       stampHeight=4,
#                       stampWidth=3))
print(
    s.possibleToStamp(grid=[[1, 1, 1, 1], [0, 0, 0, 0], [0, 0, 0, 0],
                            [0, 0, 0, 0], [0, 0, 0, 0]],
                      stampHeight=4,
                      stampWidth=3))
